# 5월 25일 조환규
# 그래프 G의 한 정점에서 출발하여 더 이상 진행하지 못할 때 까지 가는 path
# 이름하여 maximal path
# 모든 maximal path를 출력
# 부산 국제 마라톤을 이 방법, baxktrack으로 풀 수 있음
# 닥치고 모든 가능한 경로를 조사함.

def All_maximal_path(graph, start):
    def dfs(current, path):

        path.append(current)   # 현재 경로에 현재 노드 추가

        # 더 이상 진행할 수 없는 경우 (리프 노드에 도달)
        if not graph[current] or all(node in path for node, _ in graph[current]):
            # 현재 경로를 결과에 추가 (복사본 저장)
            all_paths.append(path.copy())
        else: # 인접 노드들에 대해 DFS 수행
            for neighbor, _ in graph[current]:
                if neighbor not in path:
                    dfs(neighbor, path)

        # 백트래킹 (경로에서 현재 노드 제거)
        path.pop()

    all_paths = []
    dfs(start, [])
    return( all_paths )


# 가중치 그래프 예시 (인접 리스트 형태)
weighted_graph = {
    'A': [('B', 5), ('C', 2)],
    'B': [('A', 5), ('D', 4), ('E', 2)],
    'C': [('A', 2), ('F', 3), ('E',4)],
    'D': [('B', 4)],
    'E': [('B', 2), ('C',4),  ('F', 1)],
    'F': [('C', 3), ('E', 1)]
}

# 'A'에서 시작하는 가장 긴 경로 찾기
start_vertex = 'A'
print(f">  출발 vertex = {start_vertex}")
print(f"\n ---- {start_vertex}에서 출발하는 모든 maximal path ------")
Upath = All_maximal_path(weighted_graph, start_vertex)
for i, apath in enumerate( Upath, start=1) :
    print(f"> {i:2}. {apath}")

# 가장 긴 경로 찾기
longest_path = max( Upath, key=len, default=[])
print(f"\n> 가장 긴 DFS 경로 (시작 정점 {start_vertex}):")
print(" → ".join(longest_path))